Spatial Network
   HOME

TheInfoList



OR:

A spatial network (sometimes also
geometric graph Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometr ...
) is a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
in which the vertices or
edges Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...
are ''spatial elements'' associated with
geometric Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ca ...
objects, i.e., the nodes are located in a space equipped with a certain metric.M. Barthelemy, "Morphogenesis of Spatial Networks", Springer (2018). The simplest mathematical realization of spatial network is a lattice or a random geometric graph (see figure in the right), where nodes are distributed uniformly at random over a two-dimensional plane; a pair of nodes are connected if the
Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore o ...
is smaller than a given neighborhood radius. Transportation and mobility networks,
Internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a ''internetworking, network of networks'' that consists ...
, mobile phone networks,
power grids An electrical grid is an interconnected network for electricity delivery from producers to consumers. Electrical grids vary in size and can cover whole countries or continents. It consists of:Kaplan, S. M. (2009). Smart Grid. Electrical Power ...
, social and contact networks and biological neural networks are all examples where the underlying space is relevant and where the graph's
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
alone does not contain all the information. Characterizing and understanding the structure, resilience and the evolution of spatial networks is crucial for many different fields ranging from urbanism to epidemiology.


Examples

An urban spatial network can be constructed by abstracting intersections as nodes and streets as links, which is referred to as a transportation network. One might think of the 'space map' as being the negative image of the standard map, with the open space cut out of the background buildings or walls.Hillier B, Hanson J, 1984, The social logic of space (Cambridge University Press, Cambridge, UK).


Characterizing spatial networks

The following aspects are some of the characteristics to examine a spatial network: * Planar networks In many applications, such as railways, roads, and other transportation networks, the network is assumed to be planar. Planar networks build up an important group out of the spatial networks, but not all spatial networks are planar. Indeed, the airline passenger networks is a non-planar example: Many large airports in the world are connected through direct flights. * The way it is embedded in space There are examples of networks, which seem to be not "directly" embedded in space. Social networks for instance connect individuals through friendship relations. But in this case, space intervenes in the fact that the connection probability between two individuals usually decreases with the distance between them. * Voronoi tessellation A spatial network can be represented by a
Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed ...
, which is a way of dividing space into a number of regions. The dual graph for a Voronoi diagram corresponds to the
Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...
for the same set of points. Voronoi tessellations are interesting for spatial networks in the sense that they provide a natural representation model to which one can compare a real world network. * Mixing space and topology Examining the topology of the nodes and edges itself is another way to characterize networks. The distribution of
degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...
of the nodes is often considered, regarding the structure of edges it is useful to find the
Minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
, or the generalization, the Steiner tree and the relative neighborhood graph.


Probability and spatial networks

In "real" world many aspects of networks are not deterministic - randomness plays an important role. For example, new links, representing friendships, in social networks are in a certain manner random. Modelling spatial networks in respect of stochastic operations is consequent. In many cases the
spatial Poisson process In probability, statistics and related fields, a Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space with the essential feature that the points occur independently of ...
is used to approximate data sets of processes on spatial networks. Other stochastic aspects of interest are: * The Poisson line process * Stochastic geometry: the Erdős–Rényi graph *
Percolation theory In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnecte ...


Approach from the theory of space syntax

Another definition of spatial network derives from the theory of space syntax. It can be notoriously difficult to decide what a spatial element should be in complex spaces involving large open areas or many interconnected paths. The originators of space syntax, Bill Hillier and Julienne Hanson use axial lines and convex spaces as the spatial elements. Loosely, an axial line is the 'longest line of sight and access' through open space, and a convex space the 'maximal convex polygon' that can be drawn in open space. Each of these elements is defined by the geometry of the local boundary in different regions of the space map. Decomposition of a space map into a complete set of intersecting axial lines or overlapping convex spaces produces the axial map or overlapping convex map respectively. Algorithmic definitions of these maps exist, and this allows the mapping from an arbitrary shaped space map to a network amenable to graph mathematics to be carried out in a relatively well defined manner. Axial maps are used to analyse urban networks, where the system generally comprises linear segments, whereas convex maps are more often used to analyse building plans where space patterns are often more convexly articulated, however both convex and axial maps may be used in either situation. Currently, there is a move within the space syntax community to integrate better with
geographic information system A geographic information system (GIS) is a type of database containing geographic data (that is, descriptions of phenomena for which location is relevant), combined with software tools for managing, analyzing, and visualizing those data. In a ...
s (GIS), and much of the
software Software is a set of computer programs and associated software documentation, documentation and data (computing), data. This is in contrast to Computer hardware, hardware, from which the system is built and which actually performs the work. ...
they produce interlinks with commercially available GIS systems.


History

While networks and graphs were already for a long time the subject of many studies in mathematics, physics, mathematical sociology,
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, spatial networks have been also studied intensively during the 1970s in quantitative geography. Objects of studies in geography are inter alia locations, activities and flows of individuals, but also networks evolving in time and space.P. Haggett and R.J. Chorley. ''Network analysis in geog- raphy''. Edward Arnold, London, 1969. Most of the important problems such as the location of nodes of a network, the evolution of transportation networks and their interaction with population and activity density are addressed in these earlier studies. On the other side, many important points still remain unclear, partly because at that time datasets of large networks and larger computer capabilities were lacking. Recently, spatial networks have been the subject of studies in Statistics, to connect probabilities and stochastic processes with networks in the real world.


See also

*
Hyperbolic geometric graph A hyperbolic geometric graph (HGG) or hyperbolic geometric network (HGN) is a special type of spatial network where (1) latent coordinates of nodes are sprinkled according to a probability density function into a hyperbolic space of constant nega ...
* Spatial network analysis software *
Cascading failure A cascading failure is a failure in a system of interconnected parts in which the failure of one or few parts leads to the failure of other parts, growing progressively as a result of positive feedback. This can occur when a single part fails, in ...
*
Complex network In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real ...
* Planar graphs *
Percolation theory In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnecte ...
* Modularity (networks) *
Random graphs In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...
* Topological graph theory *
Small-world network A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a sm ...
* Chemical graph * Interdependent networks


References

* * * {{DEFAULTSORT:Spatial Network * Architectural theory Environmental design Environmental psychology Application-specific graphs Graph theory